强连通分量

一.强连通分量的定义

有向图G中,如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径(即两点互相可达),则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。

一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次。

二.实现算法

1.Kosaraju算法

1.引入

我们先来看这样一张图,这是一个有两个强联通分量的一个有向图。如果我们对这个有向图进行遍历,我们如果是从A这边开始,那么只需要一个DFS就可以搜索完整个有向图,但我们如果从B这边开始,则需要两个DFS。很显然,我们这个有向图有两个强联通分量,那么,我们选择合适的起始位置(B这边的点)才能得到正确的答案。

Kosaraju算法就是寻找合适的起点,记录搜索次数。

2.算法流程

1、随意给起点进行DFS,每次在DFS回溯的过程中进行标记,得到一个后序遍历的顺序的表。

2、对原图G进行反向,得到反图R,按照步骤1中得到的表,从后往前进行DFS遍历。

3、在步骤2中,使用了多少次的DFS,就有多少个强联通分量。

代码如下:(s为后续遍历表)


void dfs1( int u ) {
	vis[ u ] = 1;
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) dfs1( v );
	}
	s.push_back( u );
}
void dfs2( int u ) {
	belong[ u ] = k;
	for( int i = 0 ; i < dis_Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
		if( !belong[ v ] ) dfs2( v );	
    }
}
void Kosaraju() {
		for( int i = 1 ; i <= n ; i ++ )
			if( !vis[ i ] ) dfs( i );
		for( int i = n - 1 ; i >= 0 ; i -- ) {
			if( !belong[ s[ i ] ] ) {
				k++;
				dfs2( s[ i ] );
			}
		}
}

3.复杂度分析

两次dfs遍历,复杂度Θ(2n)\Theta(2*n)


2.tarjan算法

1.引入

Tarjan算法是基于DFS的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

2.算法流程

定义dfn[u]dfn[u]为节点u的搜索次序编号(dfsdfs序),low[u]low[u]为u或u的子树能追溯到的最早的栈中节点。初始化时,dfn[u]=low[u]=dfn[u]=low[u]=编号​。

将搜索到的u压入栈中,枚举所有u出去的边。

1.如果v没有被访问,那么访问v,并在回溯时,计算low[u]=min(low[u],low[v])low[u]=min(low[u],low[v])

2.如果v在栈内,说明当前已经构成一个环,那么low[u]=min(low[u],dfn[v])low[u]=min(low[u],dfn[v]).

3.当u没有下一个节点可以搜索时,判断dfn[u]dfn[u]是否等于low[u]low[u],如果相等,则将栈顶元素v退栈,直到退出u为止,这次退出的所有点即为一个连通分量(它们构成了一个环)。注意,当u=v时,也要退栈,此时u本身是一个强连通分量。

代码如下:

void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	is[ u ] = 1;
	S.push( u );
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] ) {
			low[ u ] = Min( low[ u ] , dfn[ v ] );
		} 
	}
	
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
            is[ v ] = 0;
		}while( u != v );
	}
}

3.复杂度分析

只需一次dfs遍历,复杂度Θ(n)\Theta(n)


三.例题

1.HDU P1269 (迷宫城堡)

模板题,不多讲,判断强连通分量个数是否为一即可。

注意在多组数据时将各种量清空。代码如下:

#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

const int MAXN = 10005;
int n,m,a,b,depth,num;
int dfn[ MAXN + 5 ] , low[ MAXN + 5];
stack< int > S;
vector< int > Graph[ MAXN + 5];
bool is[ MAXN + 5 ];

int Min( int x , int y ) {
	return x < y ? x : y;
}
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	is[ u ] = 1;
	S.push( u );
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] ) {
			low[ u ] = Min( low[ u ] , dfn[ v ] );
		} 
	}
	
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
                        is[ v ] = 0;
		}while( u != v );
		
	}
}
int main( ) {
	while( 1 ) {
		scanf("%d %d",&n,&m);
		if( n == 0 && m == 0 )
			return 0;
		
		while( !S.empty() )
			S.pop();
		for( int i = 1 ; i <= MAXN ; i ++ )
			Graph[ i ].clear( );
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d",&a,&b);
			Graph[ a ].push_back( b );
		}
		
		depth = num = 0;
		memset( dfn , 0 , sizeof( dfn ) );
		memset( low , 0 , sizeof( low ) );
		memset( is , 0 , sizeof( is ) );
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		if( num == 1 )
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}

2.HDU P1827 (Summer Holiday)

首先建图,求出所有的强连通分量,并进行缩点。缩点的同时,找出所有分量的入度,如果入度为0,那么消耗就为这个强连通分量内的所有人的花费最少的那个人,因为只需通知花费最小的就可以通知整个分量。如果不为0,说明有其他分量可以通知该分量,就没有花费。

代码如下:

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1000;
int n,m,a,b,cost[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > S;

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth;
int belong[ MAXN + 5 ] , lit_cost[ MAXN + 5 ] , num;
bool is[ MAXN + 5 ];
int In_num[ MAXN + 5 ];

int Min( int x , int y ) {
	return x < y ? x : y;
}
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	S.push( u ) ; is[ u ] = 1;
	
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		} 
		else if( is[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = S.top( );
			S.pop( );
			is[ v ] = 0;
			
			belong[ v ] = num;
			lit_cost[ num ] = Min( lit_cost[ num ] , cost[ v ] );
		}while( u != v );
	}
}

void Memset( ) {
	num = depth = 0;
	for( int i = 1 ; i <= MAXN ; i ++ )
		Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
	while( !S.empty() ) S.pop();
	memset( lit_cost , 0x3f , sizeof( lit_cost ) );
	memset( dfn , 0 , sizeof( dfn ) );
	memset( low , 0 , sizeof( low ) );
	memset( belong , 0 , sizeof( belong ) );
	memset( is , 0 , sizeof( is ) );
	memset( In_num , 0 , sizeof( In_num ) );
}
int main( ) {
	while( ~scanf("%d %d",&n,&m) ) {
		Memset( );
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%d",&cost[ i ]);
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d",&a,&b);
			Graph[ a ].push_back( b );
		}
		
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		for( int i = 1 ; i <= n ; i ++ )
			for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
				if( belong[ i ] != belong[ Graph[ i ][ j ] ] ) {
					lit_Graph[ belong[ i ] ].push_back( belong[ Graph[ i ][ j ] ] );
					In_num[ belong[ Graph[ i ][ j ] ] ] ++;
				}
		int Ans = 0 , tot = 0;
		for( int i = 1 ; i <= num ; i ++ ) {
			if( In_num[ i ] == 0 )
				Ans += lit_cost[ i ];
			else
				tot ++;
		}
		printf("%d %d\n",num - tot,Ans);
	}
	return 0;
}
3.HDU P2767 (Proving Equivalences)

先求出k个强连通分量,并记录这些强连通分量中,入度为0和出度为0的个数,最终要添加的边数就是这两个中的最大值。

4.HDU P3861 ( The King’s Problem)

首先对强连通分量进行缩点,得到一个有向无环图(DAG)图,最后就是一个在一个DAG图上求最小路径覆盖,直接用一个二分图匹配即可。

5.POJ P3114 (Countries in War )

首先对强连通分量进行缩点,得到一个有向图,然后跑一遍最短路即可,建议用spfa。

代码如下:

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1000;
int n,m,x,y,z,t;
struct node{
	int v,w;
	node(){}
	node( int V , int W ) {
		v = V;
		w = W;
	}
};
vector< node > Graph[ MAXN + 5 ] , lit_Graph[ MAXN + 5 ];
stack< int > s;

int Max( int x , int y ) {
	return x > y ? x : y;
}
int Min( int x , int y ) {
	return x < y ? x : y;
}

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , belong[ MAXN + 5 ];
int num , depth;
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	s.push( u );
	is[ u ] = 1;
	
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ].v;
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = Min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] )
			low[ u ] = Min( low[ u ] , dfn[ v ] );
	}
	if( dfn[ u ] == low[ u ] ) {
		int v;
		num ++;
		do{
			v = s.top( );
			s.pop( ) , is[ v ] = 0;
			belong[ v ] = num;
		}while( u != v );
	}
}

int dis[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void spfa( int s ) {
	queue< int > Q;
	memset( dis , 0x3f , sizeof( dis ) );
	memset( vis , 0 , sizeof( vis ) );
	dis[ s ] = 0 , vis[ s ] = 1;
	Q.push( s );
	
	while( !Q.empty( ) ) {
		int u = Q.front( );
		vis[ u ] = 0;
		Q.pop( );
		
		for( int i = 0 ; i < lit_Graph[ u ].size( ) ; i ++ ) {
			int v = lit_Graph[ u ][ i ].v , w = lit_Graph[ u ][ i ].w;
			if( dis[ u ] + w < dis[ v ] ) {
				dis[ v ] = dis[ u ] + w;
				if( !vis[ v ] )
					Q.push( v ) , vis[ v ] = 1;
			}
		}
	}
}

void Memset( ) {
	depth = num = 0;
	memset( is , 0 , sizeof( is ) );
	memset( dfn , 0 , sizeof( dfn ) );
	memset( low , 0 , sizeof( low ) );
	memset( belong , 0 , sizeof( belong ) );
	for( int i = 1 ; i <= MAXN ; i ++ )	
		Graph[ i ].clear( ) , lit_Graph[ i ].clear( );
	while( !s.empty( ) ) s.pop( );
}
int main( ) {
	while( scanf("%d %d",&n,&m) && n ) {
		Memset( );
		for( int i = 1 ; i <= m ; i ++ ) {
			scanf("%d %d %d",&x,&y,&z);
			Graph[ x ].push_back( node( y , z ) );
		}
		for( int i = 1 ; i <= n ; i ++ )
			if( !dfn[ i ] ) Tarjan( i );
		
		for( int i = 1 ; i <= n ; i ++ )
			for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ )
				if( belong[ i ] != belong[ Graph[ i ][ j ].v ] )
					lit_Graph[ belong[ i ] ].push_back( node( belong[ Graph[ i ][ j ].v ] , Graph[ i ][ j ].w ) );
		
		scanf("%d",&t);
		while( t -- ) {
			scanf("%d %d",&x,&y);
			x = belong[ x ] , y = belong[ y ];
			spfa( x );
			if( dis[ y ] == 0x3f3f3f3f )
				printf("Nao e possivel entregar a carta\n");
			else
				printf("%d\n",dis[ y ]);
		}
		printf("\n");
	}
	return 0;
}